#include <bits/stdc++.h>
using namespace std;

/*
976. 三角形的最大周长
已解答
简单
相关标签
premium lock icon
相关企业
给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

 

示例 1：

输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成一个三角形:1 2 2。
示例 2：

输入：nums = [1,2,1,10]
输出：0
解释：
你不能用边长 1,1,2 来组成三角形。
不能用边长 1,1,10 来构成三角形。
不能用边长 1、2 和 10 来构成三角形。
因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。
 

提示：

3 <= nums.length <= 104
1 <= nums[i] <= 106
*/

// 法一
class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        // i初始化为n-3：对应首次检查的三个最大元素（nums[i], nums[i+1], nums[i+2] = nums[n-3], nums[n-2], nums[n-1]）
        int i = n - 3;
        // 初始化a/b/c为首次检查的三个元素（a≤b≤c，符合三角形判定的边长顺序）
        int a = nums[i + 1], b = nums[i + 2], c;

        // 从大到小遍历连续的三个元素，寻找首个能组成三角形的组合
        while (i >= 0) {
            // 更新三边：保持a≤b≤c的顺序，每次左移一位（纳入更小的边长，替换最大的边c）
            c = b;    // 原b变为新c（最大边）
            b = a;    // 原a变为新b（中间边）
            a = nums[i];  // 新纳入的左移边长作为a（最小边）
            // 三角形判定：因a≤b≤c，只需满足最小两边和>最大边（a+b>c），即可组成面积非零的三角形
            if (a + b > c) {
                return a + b + c; // 找到最大周长，直接返回（贪心：越大的边组合先检查，首次满足即最大）
            }
            i--; // 继续左移检查更小的边组合
        }
        return 0;
    }
};

// 法二
class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        int n = nums.size();
        if (n < 3)  return 0;

        sort(nums.begin(), nums.end());

        // 最长的 在最前面  连续的最长肯定在前面 满足a + b > c 
        for (int i = n - 1; i >= 2; i--) {
            if (nums[i - 2] + nums[i - 1] > nums[i])
                return nums[i - 2] + nums[i - 1] + nums[i];
        }
        return 0;
    }
};